#include <iostream>
#include <map>
#include <utility>
#include <set>
#include <fstream>
using namespace std;

//оба класса должны иметь <
template <class vertexData,class edgeData>
class graph{
public:
    graph(){}
    void addEdge(vertexData& first, vertexData& second, edgeData& data) {
        pair< vertexData,edgeData > pair1 (second,data);
        edgeMap.insert ( pair<vertexData,pair< vertexData,edgeData > >(first,pair1));
        vertexSet.insert(first);
        vertexSet.insert(second);
    }

    void addVertex(vertexData& vertex){
        vertexSet.insert(vertex);
    }

    typedef typename set < vertexData >::iterator vertexListIterator;
    typedef typename multimap< vertexData,pair< vertexData,edgeData > >::iterator edgeListIterator;
    class edgeIterator;
    class vertexIterator{
    friend class edgeIterator;
    public:


        vertexIterator() {}
        vertexIterator(const graph<vertexData, edgeData>* g, const vertexListIterator& v){
            graphPointer = g;
            listIterator = v;
        }
        ~vertexIterator() {}
        //TODO
        vertexData operator *() {
            return *listIterator;
        }
        const vertexData& operator *() const{
            return *listIterator;
        }
        edgeIterator beginEdges();
        const edgeIterator beginEdges() const;
        edgeIterator endEdges();
        const edgeIterator endEdges() const;

        vertexIterator(const vertexIterator& other){
                graphPointer = other.graphPointer;
                listIterator = other.listIterator;
            }

       vertexIterator& operator =(const vertexIterator& other){
            graphPointer == other.graphPointer;
            listIterator == other.listIterator;
            return *this;
        }

        vertexIterator& operator ++(){
            listIterator ++;
            return *this;
        }

        //int GetIndexOfCurrentVertex() const;

        //bool operator <(const vertexIterator& other) const;

        bool operator ==(const vertexIterator& other) const{
            return (graphPointer == other.graphPointer)&&(listIterator == other.listIterator);
        }
        bool operator !=(const vertexIterator& other) const {
            return !(*this == other);
        }

    private:
        const graph<vertexData, edgeData>* graphPointer;
        vertexListIterator listIterator;
    };


    class edgeIterator{
    public:
        edgeIterator() {};
        edgeIterator(const edgeIterator& other){
            graphPointer = other.graphPointer;
            listIterator = other.listIterator;
        }

        edgeIterator(const graph<vertexData, edgeData>* g , const edgeListIterator& e){
            graphPointer = g;
            listIterator = e;
        }

        ~edgeIterator() {};

        edgeData& operator*(){
            return listIterator->second.second;
        }

        const edgeData& operator*() const{
            return listIterator->second.second;
        }

        vertexData first(){
            return listIterator->first;
        }

        vertexData second(){
            return listIterator->second.first;
        }

        vertexIterator beginVertex(){
            vertexIterator vertex(graphPointer, graphPointer->vertexSet.find(listIterator->first));
            return vertex;
        }

        const vertexIterator beginVertex() const{
            vertexIterator vertex(graphPointer, graphPointer->vertexSet.find(listIterator->first));
            return vertex;
        }
        vertexIterator endVertex(){
            vertexIterator vertex(graphPointer, graphPointer->vertexSet.find(listIterator->second->first));
            return vertex;
        }

        const vertexIterator endVertex() const{
            vertexIterator vertex(graphPointer, graphPointer->vertexSet.find(listIterator->second->first));
            return vertex;
        }

        edgeIterator& operator =(const edgeIterator& other){
            graphPointer = other.graphPointer;
            listIterator = other.listIterator;
            return *this;
        }

        edgeIterator& operator ++(){
            listIterator++;
            return *this;
        }

        bool operator ==(const edgeIterator& other) const{
            return (graphPointer == other.graphPointer)&&(listIterator == other.listIterator);
        }
        bool operator !=(const edgeIterator& other) const {
            return !operator==(other);
        }

    private:

        const graph<vertexData, edgeData>* graphPointer;
        edgeListIterator listIterator;
    };

        //graph(int vertexNum = 0);
        //graph(VertexType vertexZeroVal, EdgeType edgeZeroVal, int vertexNum = 0);

        /*vertexIterator addVertexWeight(int vertexNum, const VertexType& value);
        edgeIterator addEdge(int from, int to, const EdgeType& weight);
        */

        vertexIterator vertexBegin(){

            vertexIterator vertex (this,vertexSet.begin());
            return vertex;
        }

        vertexIterator vertexEnd(){
            vertexIterator vertex (this,vertexSet.end());
            return vertex;
        }

        vertexIterator findVertex(const vertexData& vertex) {
            for (graph<vertexData,edgeData>::vertexIterator v = this->vertexBegin(); v != this->vertexEnd(); ++v){
               if (*v == vertex){
                    return v;
                }
           }
           return this->vertexEnd();
        }

        edgeIterator edgeBegin(){
            edgeIterator edge (this,edgeMap.begin());
            return edge;
        }

        edgeIterator edgeEnd(){
            edgeIterator edge (this,edgeMap.end());
            return edge;
        }


/*
        int GetVertexCount() const;
        EdgeType GetEdgeTypeZeroValue() const { return edgeTypeZeroValue; }
        VertexType GetVertexTypeZeroValue() const { return vertexTypeZeroValue; }

        bool existsEdge(int i) const
        {
            return matrix[i] != nullptr;
        }

*/
    ~graph(){}
private:
    multimap< vertexData,pair< vertexData,edgeData > > edgeMap;
    set <vertexData> vertexSet;
};

template<class vertexData,class edgeData>
typename graph<vertexData,edgeData>::edgeIterator graph<vertexData,edgeData>::vertexIterator::beginEdges(){
    pair <edgeListIterator, edgeListIterator> ret;
    ret = graphPointer->edgeMap.equal_range(*listIterator);
    edgeIterator edge (graphPointer,ret.first);
    return edge;
}

template<class vertexData,class edgeData>
const typename graph<vertexData,edgeData>::edgeIterator graph<vertexData,edgeData>::vertexIterator::beginEdges() const{
    pair <edgeListIterator, edgeListIterator> ret;
    ret = graphPointer->edgeMap.equal_range(*listIterator);
    edgeIterator edge (graphPointer,ret.first);
    return edge;
}
template<class vertexData,class edgeData>
typename graph<vertexData,edgeData>::edgeIterator graph<vertexData,edgeData>::vertexIterator::endEdges(){
    pair <edgeListIterator, edgeListIterator> ret;
    ret = graphPointer->edgeMap.equal_range(*listIterator);
    edgeIterator edge (graphPointer,ret.second);
    return edge;
}
template<class vertexData,class edgeData>
const typename graph<vertexData,edgeData>::edgeIterator graph<vertexData,edgeData>::vertexIterator::endEdges() const{
    pair <edgeListIterator, edgeListIterator> ret;
    ret = graphPointer->edgeMap.equal_range(*listIterator);
    edgeIterator edge (graphPointer,ret.second);
    return edge;
}

/////////////////




template <class vertexData, class edgeData>
void FordBelman(graph<vertexData,edgeData> g, typename graph<vertexData,edgeData>::vertexIterator start){
    typedef graph < vertexData,edgeData > graphType;
    typedef map< vertexData,edgeData > mapType;
     typedef pair< vertexData,edgeData > pairType;
    mapType fordMap;
    fordMap.insert(make_pair( *start,0));
    int size = 0;
    for (typename graphType::vertexIterator v = g.vertexBegin(); v != g.vertexEnd(); ++v){
        fordMap.insert(pair<vertexData,edgeData>(*v,30000));
        size++;
    }
        for (int j = 0; j < size; ++j){
            for (typename graphType::edgeIterator edge = g.edgeBegin(); edge != g.edgeEnd(); ++edge){
                if (fordMap.find(edge.first())->second < 30000 && fordMap.find(edge.second())->second > fordMap.find(edge.first())->second + (*edge)){
                        typename map<vertexData,edgeData>::iterator i = fordMap.find(edge.second());
                        fordMap.erase(i);
                        fordMap.insert(pairType(edge.second(),fordMap.find(edge.first())->second + *edge));
                    }
            }
        }
        std::ofstream out ("OUTPUT.TXT");
        for (typename mapType::iterator i = fordMap.begin(); i != fordMap.end(); ++i){
            out << i->second<<" ";
        }
}


int main()
{
    graph <int,int> g;
    int a,b,w,n,m;
    std::ifstream in ("INPUT.TXT");

    in>>n>>m;
    for (int i = 1; i <= n; i++ ){
        g.addVertex(i);
    }
    for(int i = 0; i < m; i++){
        in>>a>>b>>w;
        g.addEdge(a,b,w);
    }
    graph<int,int>::vertexIterator start = g.findVertex(1);
    FordBelman<int,int>(g,start);
    return 0;
}
